package cn.zifangsky.tree.binarytree.questions;

import org.junit.Test;

import cn.zifangsky.queue.LinkQueue;
import cn.zifangsky.tree.binarytree.BinaryTreeNode;

/**
 * 在二叉树中插入一个元素
 * @author zifangsky
 *
 */
public class Question5 {
	
	/**
	 * 通过层次遍历向二叉树中插入一个元素
	 * 思路：
	 * 		因为是二叉树所以可以在任意地方插入元素，因此找到一个左孩子或者右孩子节点为空的节点，插入该元素即可
	 * 
	 * @时间复杂度 O(n)
	 * @param root
	 */
	public void insertElementByQueue(BinaryTreeNode<Integer> root,int data){
		
		LinkQueue<BinaryTreeNode<Integer>> queue = new LinkQueue<>();
		if(root != null){
			queue.push(root);
		}
		
		while (!queue.isEmpty()) {
			BinaryTreeNode<Integer> temp = queue.pop(); //出队
			
			if(temp.getLeft() == null){
				temp.setLeft(new BinaryTreeNode<Integer>(data));
				return;
			}else if(temp.getRight() == null){
				temp.setRight(new BinaryTreeNode<Integer>(data));
				return;
			}else{
				queue.push(temp.getLeft());
				queue.push(temp.getRight());
			}
		}
	}
	
	/**
	 * 层次遍历：使用队列辅助操作
	 * @时间复杂度 O(n)
	 * @param root
	 */
	public void levelOrder(BinaryTreeNode<Integer> root){
		LinkQueue<BinaryTreeNode<Integer>> queue = new LinkQueue<>();
		if(root != null){
			queue.push(root);
		}
		
		while (!queue.isEmpty()) {
			BinaryTreeNode<Integer> temp = queue.pop();
			System.out.print(temp.getData() + " ");
			
			if(temp.getLeft() != null){
				queue.push(temp.getLeft());
			}
			if(temp.getRight() != null){
				queue.push(temp.getRight());
			}
		}
	
	}
	
	/**
	 * 测试用例
	 */
	@Test
	public void testMethods(){
		/**
		 * 使用队列构造一个供测试使用的二叉树
		 *     1
		 *   2    3
		 * 4  5  6  7
		 *   8 9  
		 */
		LinkQueue<BinaryTreeNode<Integer>> queue = new LinkQueue<BinaryTreeNode<Integer>>();
		BinaryTreeNode<Integer> root = new BinaryTreeNode<>(1); //根节点
		
		queue.push(root);
		BinaryTreeNode<Integer> temp = null;
		for(int i=2;i<10;i=i+2){
			BinaryTreeNode<Integer> tmpNode1 = new BinaryTreeNode<>(i);
			BinaryTreeNode<Integer> tmpNode2 = new BinaryTreeNode<>(i+1);
			
			temp = queue.pop();
			
			temp.setLeft(tmpNode1);
			temp.setRight(tmpNode2);
			
			if(i != 4)
				queue.push(tmpNode1);
			queue.push(tmpNode2);
		}

		insertElementByQueue(root,10);
		System.out.println("插入之后使用层次遍历的结果是： ");
		levelOrder(root);

	}

}
